#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    void duplicateZeros(vector<int>& arr)
    {
        int cur = 0, dest = -1;
        //找最后一个复写的数
        while (cur < arr.size())
        {
            if (arr[cur] != 0)
                dest++;
            else
                dest += 2;
            if (dest >= arr.size() - 1) break;
            cur++;
        }
        //处理一下边界情况
        if (dest == arr.size())
        {
            arr[dest - 1] = 0;
            cur--;
            dest -= 2;
        }
        //复写操作
        while (cur >= 0)
        {
            if (arr[cur] != 0)
            {
                arr[dest--] = arr[cur--];
            }
            else
            {
                arr[dest--] = arr[cur];
                arr[dest--] = arr[cur--];

            }
        }
    }
};
int main()
{
    vector<int> v;
    int arr[] = { 1,0,2,3,0,4,5,0 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < sz; i++)
    {
        v.push_back(arr[i]);
    }
    Solution().duplicateZeros(v);
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
	return 0;
}
/*
题目链接:https://leetcode.cn/problems/duplicate-zeros/description/
*/